#include <iostream>
using namespace std;

const int MAX_STR_LEN = 100;
const int END_OF_DATA = -1;
const int MAX_ARR_LEN = 100;

void printBoolRes(bool flag);
void printArr(int arr[], int size);
int readArray(int data[]);
void bubbleSort(int data[], int size);

int *find_elements(int n);
int numerology(char str[]);
int count_lower(char* str);
bool exactly_n(int arr[], int size, int num, int repeats);
bool is_contained(int setA[], int aSize, int setB[], int bSize);
void put_from_both_sides(int arr[], int size, int res[]);
int set_diff_size(int arr1[], int n1, int arr2[], int n2);
bool one_one(int arr[], int size);
int find_zero(int nums[], int n);
bool repeats2Times(int nums[], int size);
bool repeat_k_times(int nums[], int size, int k);
int *find_ruling(int nums[], int size, int *newSizePr);

//find_elements
//input: an integer
//output: an array with a series finalize with n.
//runtime: O(n)
int *find_elements(int n)
{
	int *ret;
	int i; //looper
	ret = new int[n];
	ret[0] = 1;
	for(i=1;i<n;i++)
		ret[i] = ret[i-1] + i;
	return ret;
}
//numerology
//input: a string
//output: the numeric value of the string
//runtime: O(n)
int numerology(char str[])
{
	int numer_value; // value to return
	int cur_int; // the current numeric value of the letter.
	int i; //looper
	numer_value = 0;
	i=0;
	while(str[i] != '\0')
	{
		cur_int = str[i] - 'a' + 1;
		if(cur_int <= 10)
			numer_value += cur_int;
		else if(cur_int<=18)
			numer_value += (cur_int - 9)*10;
		else
			numer_value += (cur_int - 18)*100;
		i++;

	}
	return numer_value;

}

//count_lower
//input: a string
//output: amount of lower case letters
//runtime: O(n)
int count_lower(char *str)
{
	char ch; // current char
	ch = str[0];
	if(ch == '\0') return 0;
	if((ch >= 'a') && (ch <= 'z')) 
		return 1 + count_lower(str + 1);
	return count_lower(str + 1);
}

//exactly_n
//input: an array, it size, a number and amount of repeats
//output: the function will return true only if the numer appears as stated in the repeat.
//runtime: O(n)
bool exactly_n(int arr[], int size, int num, int repeats)
{
	int cur; //current integer
	cur = arr[size - 1];
	if(repeats<0) return false;
	if(size==1)
	{
		if( cur != num) return repeats == 0;
		return repeats == 1;
	}
	if(cur == num) return exactly_n(arr, size-1, num, repeats - 1);
	return exactly_n(arr, size - 1, num, repeats);

}

//is_contained
//input: two sorted arrays and their size
//output: whether the first array is contained in the second
//runtime: O(n)
bool is_contained(int set_a[], int a_size, int set_b[], int b_size)
{
	int cur_a, cur_b; //current selections
	if(a_size == 0) return true;
	if(b_size == 0) return false;
	cur_a = set_a[0];
	cur_b = set_b[0];
	if(cur_a == cur_b) return is_contained(set_a + 1, a_size -1, set_b + 1, b_size - 1);
	if(cur_b < cur_a) return is_contained(set_a, a_size, set_b + 1, b_size - 1);
	return false;
	
}

//put_from_both_sides
//input: array and it size
//output: an array with shuffled members
//runtime: O(n)
void put_from_both_sides(int arr[], int size, int res[])
{
	if(size == 0) return;
	if(size<2)
	{
		res[0] = arr[0];
		return;
	}
	res[0] = arr[0];
	res[1] = arr[size - 1];
	put_from_both_sides(arr + 1, size - 2, res + 2);
}

//set_diff_size
//input: two sorted arrays and their size
//output: the amount of numbers appearing in the first but not in the other.
//runtime: O(n)
int set_diff_size(int arr1[], int n1, int arr2[], int n2)
{
	int cur_a, cur_b; //current selections
	if(n1 == 0) return 0;
	if(n2 == 0) return n1;
	cur_a = arr1[0];
	cur_b = arr2[0];
	if(cur_a == cur_b) return set_diff_size(arr1 + 1, n1 -1, arr2 + 1, n2 - 1);
	if(cur_b < cur_a) return set_diff_size(arr1, n1, arr2 + 1, n2 - 1);
	return 1 + set_diff_size(arr1 + 1, n1 - 1, arr2, n2);
}

//one_one
//input: an array and it size
//output: returns true if there are no reoccurances of the same number
//runtime: O(n)
bool one_one(int arr[], int size)
{
	int i; //looper
	int *bucket; // for bucket sort.
	int bkt_size; // the bucket array size.
	bkt_size = size*3 - 1;

	bucket = new int[bkt_size];
	for(i=0;i<bkt_size;i++)
		bucket[i] = 0;
	for(i=0;i<size;i++)
	{
		bucket[arr[i]]++;
		if(bucket[arr[i]] > 1) 
		{
			delete bucket;
			return false;
		}
	}
	delete bucket;
	return true;

}

//find_zero
//input: an array and it size
//output: the index for the zero value
//runtime: O(log(n))
int find_zero(int arr[], int size)
{
	int ret;
	if(size==0)
		return -1;
	if(arr[0] == 0)
		return 0;
	ret = find_zero(arr + 1, (size-1)/2 + 1);
	if(ret!= -1)
		return ret + 1;
	ret = find_zero(arr + size/2, (size)/2 + 1);
	if(ret!= -1)
		return ret + size/2;

}

//repeat_k_times
//input: an array it size and an integer
//output: if the array have a repeating pattern of k times.
//runtime: O(n)
bool repeat_k_times(int nums[], int size, int k)
{
	bool flag;
	int i;
	flag = true;
	if(k == 0) return 0;
	if(size == 0) return false;
	for(i=0;i<k - 1;i++)
		if(!repeats2Times(nums + i*size/k, size/k*2)) flag = false;
	return flag;

}

//find_ruling
//input: an array and it size
//output: an array with the ruling numbers in the array
//runtime: O(n)
int *find_ruling(int nums[], int size, int *res_size)
{
	int i; //looper
	int max; // the current maximun numer
	int *ret; // the array to return
	int *tmp; // a temporary array to build.
	*res_size = 0;
	tmp = new int[size];
	max = nums[0];
	for(i=1;i<size;i++)
		if(nums[i] > max)
		{
			tmp[*res_size] = nums[i];
			*res_size = *res_size + 1;
			max = nums[i];
		}
	if((*res_size) == 0) return NULL;
	ret = new int[*res_size];
	for(i=0;i<*res_size;i++)
		ret[i] = tmp[i];
	delete tmp;
	return ret;

}
int main()
{
	int choice; // for menu
	int res; // returned value from user function
	bool boolres; // returned boolean value from user function
	int i; //index for input loops
	char ch; // to read '\n' after choice
	int num, num2;  // user input
	char strin[MAX_STR_LEN]; //user string input
	int data1[MAX_ARR_LEN], data2[MAX_ARR_LEN]; //user array of input data
	int resData[MAX_ARR_LEN]; //output array from functions
	int dataSize1, dataSize2; //logical size of data
	int *respr; // return value when dynamic allocated array is expected

	cout << "Press 1 for section 1\n";
	cout << "Press 2 for section 2\n";
	cout << "Press 3 for section 3\n";
	cout << "Press 4 for section 4\n";
	cout << "Press 5 for section 5\n";
	cout << "Press 6 for section 6\n";
	cout << "Press 7 for section 7\n";
	cout << "Press 8 for section 8\n";
	cout << "Press 9 for section 9\n";
	cout << "Press 10 for section 10\n";
	cout << "Press 11 for section 11\n";

	cin >> choice;

	switch (choice)
	{
	case 1:
		for (i = 1; i <= 4; i++)
		{
			cin >> num;
			respr = find_elements(num);
			printArr(respr, num);
		}
		cout << endl;
		break;

	case 2:
		for (i = 1; i <= 4; i++)
		{
			cin >> strin;
			res = numerology(strin);
			cout << res << endl;
		}
		cout << endl;
		break;

	case 3:
		ch = cin.get(); //skipping the \n after choice
		for (i = 1; i <= 4; i++)
		{
			cin.getline(strin, MAX_STR_LEN - 1);
			res = count_lower(strin);
			cout << res << endl;
		}
		cout << endl;
		break;

	case 4:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			cin >> num >> num2;
			boolres = exactly_n(data1, dataSize1, num, num2);
			printBoolRes(boolres);
		}
		cout << endl;
		break;
	case 5:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			dataSize2 = readArray(data2);
			boolres = is_contained(data1, dataSize1, data2, dataSize2);
			printBoolRes(boolres);
		}
		cout << endl;
		break;

	case 6:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			put_from_both_sides(data1, dataSize1, resData);
			printArr(resData, dataSize1);
		}
		cout << endl;
		break;

	case 7:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			dataSize2 = readArray(data2);
			bubbleSort(data1, dataSize1);
			bubbleSort(data2, dataSize2);
			res = set_diff_size(data1, dataSize1, data2, dataSize2);
			cout << res << endl;
		}
		cout << endl;
		break;

	case 8:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			boolres = one_one(data1, dataSize1);
			printBoolRes(boolres);
		}
		cout << endl;
		break;

	case 9:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			res = find_zero(data1, dataSize1);
			cout << res << endl;
		}
		cout << endl;
		break;

	case 10:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			cin >> num;
			boolres = repeat_k_times(data1, dataSize1, num);
			printBoolRes(boolres);
		}
		cout << endl;
		break;

	case 11:
		for (i = 1; i <= 4; i++)
		{
			dataSize1 = readArray(data1);
			respr = find_ruling(data1, dataSize1, &res);
			if (respr != NULL)
				printArr(respr, res);
			else
				cout << "No Ruling numbers\n";
		}
		cout << endl;
		break;


	}
}


void printBoolRes(bool flag)
{ // This function prints true or false accoring to the value of flag

	if (flag)
		cout << "true\n";
	else
		cout << "false\n";
}

void printArr(int arr[], int size)
{ // This funct6ion prints the numbers contained in arr, where size is the logical size of arr

	int i; // index for loop

	for (i = 0; i < size; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

int readArray(int data[])
{
	int num; //input from user
	int size; //reutnred logical size 

	size = 0;
	cin >> num;
	while ((num != END_OF_DATA) && (size < MAX_ARR_LEN))
	{
		data[size++] = num;
		cin >> num;
	}

	return(size);

}

void bubbleSort(int data[], int size)
{
	int i, j; // loop index
	int temp; //for the swap

	for (i = 0; i < size - 1; i++)
	for (j = size - 2; j >= i; j--)
	{
		if (data[j] > data[j + 1])
		{
			temp = data[j];
			data[j] = data[j + 1];
			data[j + 1] = temp;
		}
	}

}

bool repeats2Times(int nums[], int size)
{

	int i;

	for (i = 0; i < size / 2; i++)
	if (nums[i] != nums[size / 2 + i])
		return (false);

	return(true);

}
